package first.forHuaWei.二分搜索;

/**
 * @ClassName LC34
 * @description:
 * @author: 荣燊
 * @create: 2021-09-05 12:28
 **/
public class LC34 {
    // 二分查找
    // 在有序数组中查找元素的第一个和最后一个位置，这里重要的是如何寻找左边界
    public static void main(String[] args) {
        int[] nums = {5, 7, 7, 8, 8, 10};
        int target = 8;
        int[] res = searchRange(nums, target);
        System.out.println(res[0]+","+res[1]);
    }

    public static int[] searchRange(int[] nums, int target) {
        int[] res = new int[2];
        int left = binarySearch1(nums, target);
        int right = binarySearch2(nums, target)-1;
        if (left <= right && right <= nums.length && nums[left] == target && nums[right] == target) {
            return new int[]{left, right};
        }
        return new int[]{-1, -1};
    }

    // 查找左边界
    public static int binarySearch1(int[] nums, int target) {
        int left = 0;
        int right = nums.length-1;
        int ans = nums.length;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] >= target) {
                right = mid - 1;
                ans = mid;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }

    // 查找右边界,不是真正的右边界
    public static int binarySearch2(int[] nums, int target) {
        int left = 0;
        int right = nums.length-1;
        int ans = nums.length;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] > target) { // 仅一个判断之差
                right = mid - 1;
                ans = mid;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
}
